package com.xj.algorithm.leetcode;

/**
 * 二进制求和
 */
public class L67_二进制相加 {

    /**
     *给定两个二进制字符串，返回他们的和（用二进制表示）。
     *
     * 输入为非空字符串且只包含数字 1 和 0。
     *
     * 示例 1:
     * 输入: a = "11", b = "1"
     * 输出: "100"
     *
     * 示例 2:
     * 输入: a = "1010", b = "1011"
     * 输出: "10101"
     */

    public static void main(String[] args) {
        System.out.println(addBinaryGood("11","1"));
        System.out.println(addBinaryGood("1010","1011"));
    }

    //自己的解法：逆序相加，注意进位。2进制
    public static String addBinary(String a, String b) {
        int alen=a.length();
        int blen=b.length();

        String result="";
        int carry=0;
        while(blen>0 && alen>0){
            int avalue= Integer.parseInt(a.substring(alen-1,alen));
            int bvalue= Integer.parseInt(b.substring(blen-1,blen));

            int tmpValue=avalue+bvalue+carry;
            carry=tmpValue/2;
            result=tmpValue%2+result;

            alen--;
            blen--;
        }
        while(alen>0){
            int avalue= Integer.parseInt(a.substring(alen-1,alen));
            int tmpValue=avalue+carry;
            carry=tmpValue/2;
            result=tmpValue%2+result;

            alen--;
        }
        while(blen>0){
            int bvalue= Integer.parseInt(b.substring(blen-1,blen));
            int tmpValue=bvalue+carry;
            carry=tmpValue/2;
            result=tmpValue%2+result;

            blen--;
        }
        if(carry>0){
            result=carry+result;
        }
        return result;
    }

    //精彩解法：使用字符的ascii进行加减，字符串长度不够，用'0'来凑
    public static String addBinaryGood(String a, String b) {
        String ans = new String();
        int carry = 0;
        for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
            int sum = 0;
            sum=sum+carry;
            sum += i >= 0 ? a.charAt(i) - '0' : 0;
            sum += j >= 0 ? b.charAt(j) - '0' : 0;
            ans=(sum % 2)+ans;
            carry = sum / 2;
        }
        ans=(carry > 0 ? carry : "")+ans;
        return ans;
    }

}
